1. Technical Field:
This invention relates to multiprocessor data processing systems having local cache storage for a plurality of processors and a global storage control unit utilizing a global storage based directory for tracking intervals of storage drawn from a pool of storage shared by a plurality of processors.
2. Description of the Related Art:
Multiprocessors are provided by the coordinated interconnection of computers for the solution of a problem. Of particular interest are multiple-instruction stream, multiple-data stream (MIMD) architectures, which link independent processing units through exchange of data and synchronization of processing operations. The problems to which MIMD architectures are beneficially applied include those where the interaction of operations are not easily predicted a priori. In computers having an MIMD architecture each processing unit can execute its own program on its own data, as contrasted with single-instruction stream, multiple-data stream (SIMD) machines in which each processor executes the same instruction set but on a data stream particular to each processor.
In designing an MIMD architecture for a computer, a developer may draw on features of two conceptual types, including one type where all memory and input/output functions are remote to the processors and shared among the processors, and a second type where all memory and input/output functions are local and private to the processors. What is common to both types of architecture is an interconnection system over which synchronizing functions are carried out and processing units exchange data. The interconnection system may be a bus or a type of network architecture. The data traffic on some types of interconnection system, typically busses, is visible to processors, storage units and input/output units. On some network architectures, however, data traffic is not visible to all processors, storage and input/output units.
The treatment of memory in a multiprocessor is a critical design matter. The extreme design types either utilize purely shared memory or purely private memory. In a shared memory all processors have access to a global, remote memory unit. In a private memory scheme all memory is local to the processors and used directly only by a single processor. Both schemes have advantages and disadvantages, which has led to architectures which blend the schemes. One such blended architecture utilizes local, private cache for each processor or group of processors and a shared, remote memory. In these systems, the local cache and the global memory occupy different levels in a memory hierarchy for the computer. All local cache units are peers in the hierarchical scheme. The shared, remote memory is called global memory and is analogous to system memory in single processor computers.
The presence of a memory hierarchy, with cache being above global memory in the hierarchy, means that a shared datum may be represented by values resident at several locations. This occurs when a particular logical address is associated with physical locations in global memory and a plurality of cache units. The existence of both cache and system memory in itself raises issues of data coherency. Data coherency is compromised by the possibility that one variable may have location dependent values at a given instant in time. Coherency is vastly complicated by the existence of peer cache units where copies of a record may be duplicated to numerous locations over a network. Incoherence in data can result from a number of sources, e.g. process migration, input/output activity, and execution of implicit or explicit storage operations by a processor.
Assuring effective synchronization of processing units demands maintaining coherence of data among peer cache units and between cache and global memory. In other words, the values stored in the various locations associated with a logical address either agree or are somehow marked as temporarily inaccessible. The problem of coherence has been addressed by utilization of coherence protocols. A coherence protocol may provide for signalling invalidity of values for variables to the various multiprocessors, for propagating updated values for variables throughout the memory hierarchy, by defining conditions under which a local processing unit will mark blocks of data in its local cache as valid and invalid, et cetera.
A number of coherence protocols have been proposed. Some of these protocols, in an effort to minimize demand for coherency communications over the interconnection system, have required a system bus based architecture for implementation. An example of such a system is seen in U.S. Pat. No. 5,025,365 to Mathur et al. Mathur teaches a snooping coherency protocol in which processors monitor interconnection system communication for data updates and messages invalidating data. However, as the number of processors in a multiprocessor increases, access to the system bus becomes ever more difficult. Thus despite a reduced burden of communication required to maintain coherence over a bus based system where bus snooping is used, degradation in performance of the multiprocessor will still occur at some point as additional processors are added. The total number of processors which can effectively be used and be interconnected by a system bus can be held below desirable levels.
For truly large, or geographically dispersed multiprocessors, non-bus based networks are used for an interconnection system. In U.S. Pat. No. 5,151,989 to Johnson et al., a coherency protocol applicable to such interconnection systems was proposed using a directory caching technique for reducing coherency related communications. In Johnson, when a data processing system ("client") interrogates another data processing system ("server") for a unit of directory information relating to a record permanently resident on the server, the server becomes enabled to automatically send additional units of directory information back to the client upon subsequent changes in the directory structure of the server system. The server maintains coherency of its records. When the server determines that it cannot maintain coherency as to a record, it informs its clients of the fact to get the clients to purge their caches of copies the affected record. However, the client may no longer be caching the record. Such communications continue to occur because the manager of the coherency protocol has no knowledge of the status of the record on the client.